Well I thought this was kinda obvious what I meant, but I guess not. What you say is a requirement (sms recovery of a cloud account) is just one of many solutions to your specific problem. I’ll just list off a few solutions below that involve neither SMS (the most insecure communication method in common use today) and only optionally a cloud account. For cimplicity sake I’ll stick to Aegis, where you can create password-protected local backups you can then put wherever you want. This password needs to be very strong for obvious reasons: I would recommend a long sentence (40 characters or more) that you can just remember, like a quote from a movie/tv show/book/poem or something, including normal punctuation as a sentence for example.

Solution 0: This is more of a trivial solution I wouldn’t actually recommend. You can allow account recovery via eMail and have your eMail not use 2fa, but a long/good password so you can login from memory (see above). This is probably more secure than SMS for the recovery-case, but less secure for the everyday use case of eMail, therefore “not recommended”.

Solution 1: USB Sticks are tiny, as in the size of a USB port (slightly longer but slimmer for USB-C). If you want to have a backup “on you”, I’m sure you can find a place where it wouldn’t get robbed with the phone/wallet. A tiny pocket somewhere, a string around your ankle, make a compartment in your shoe, or just have it with your luggage at the hotel. I’m sure you get the point. You get your new phone, you plug in the USB, you install Aegis and restore the backup.

Solution 2a: Dedicated “online” storage. This can be self hosted, or a free account of any cloud provider, but the important part is that it does NOT require 2FA and you do NOT use it for anything else. You have the backup in there. It also needs a very secure password (again: long, but easy to remember, no garbled letter nonsense), but obviously not the same as the Aegis-Backup. So you now need to remember 2 long passwords. You get your new phone, you log in, get the backup and proceed as usual.

Solution 2b: If not having 2FA is not an option for the solution above, you can have a friend/family store the 2FA on his phone. To log in, you go to the login page and enter your password (which your friend doesn’t need to know), and you ask him over the phone for the current 2FA-Code, which he tells you and you can log in, download the backup and proceed as above. I assume such a high security isn’t that critical, since you have been using something involving SMS. Restore then goes as per usual.

Solution 3: Store the whole backup with a friend and when you need it he just temporarily puts it somwhere you can access, and removes it again after. Since the backup is protected by a monster of a password, and the accessibility is temporary anyway, this isn’t security critical.

Solution 4: If you absolutely must, you can find a cloud-provider for 2FA, and use it only as the “first stage”. The only 2FA code in there is the one you need to get access to your main online storage/account where you then have your real Aegis-Backup and/or other files. Obviously this service would need to allow you to login without 2FA, and the usual password rules resulting fom that apply. You can just add the 2FA of your primary service to more than 1 app or service, or if it allows for this, you can generate multiple authenticators so you can also revoke them serperately if needed.

What I do is using synching to sync my files on my PC when I am at home. You could also manually back it up on a cloud drive.

Anyway I think it’s best practice to store somewhere recovery codes.