iCloud verification key only generates after restart

Recently my iCloud integration stopped working. When I try to reactivate it I get a dialog to enter a verification key, but I one get a verification key sent to me iPhone once I restart HA, and then the iCloud login session is no longer active.

Is there any way to fix this?