For the future, if you use yubikeys, yubico authenticator is a drop in replacement for google-authenticator and you can save your google-auth setup on multiple yubikeys. So, even if you lose one, you still have it on another. Then it is independent of the phone. Also the yubikeys themselves can be used as 2FA for google accounts. However, sadly, you can't set them up on firefox the last time I tried.