The best solution is to maintain a notebook to write you all the accounts credentials including Google Authentication codes and keep it always under you.
An even better option is to use a 2FA app such as Aegis, which allows you to export an encrypted database of all your shared secrets, which you could store on an offline medium such as a USB drive. Then, if you lose your phone and you need to recover your 2FA codes, it's as easy as downloading the app on your new phone and importing the back up.
I absolutely wouldn't recommend Authy. It is closed source. Your 2FA codes are stored in their servers. They collect a lot of information about you, including device information, email address, phone number, IP address, location, log in history, and more. If you lose access to your account, they require full KYC with copies of your ID to recover your account. This is an unnecessary security and privacy risk, for something you can do safely yourself as described above.