Doesn't help obviously if you already lost your phone, but I recommend anyone to use a third party authenticator app. Most services offer to scan a QR code to set up MFA, which can easily be backed up. Don't use Google/Microsoft authenticator apps directly. Personally I use Stratum, but any that allows export/import will do.

This. Authy and a throwaway phone added in that sits in a safe place.