I ran into that issue when my Nexus 5X died to the bootloop issue. It was enough of a pain that I just gave up and use Authy with the remote backup enabled.

I've dealt with phones dying/being lost on three separate occasions and recovering the accounts, as you've said, is a huge hassle, and I always end up screwing up at least once resulting in dealing with a round of phone support calls to get access again.