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.
That’s open to interpretation. Your current solution you thought was secure, but you used a service that as it turned out had bad security practices, which you just didn’t know (arguably couldn’t know). ANY online/cloud service that you don’t host yourself has this issue with being a black box of unkown quality. Any online service you do host has to be secured by you (or you need to trust that the base setup of that tool is “sufficiently secure”), and is in essence limited by your knowledge of the tool and technology used. Also if you’re reusing any passwords, anywhere, just stopping that practice is likely more secure in practice compared to 2fa in isolation.
2fa in general isn’t just plaing “better” than not having it, security is rarely this black and white. It also depends on what is allowed to be the “second factor”, and since yours included SMS, it really wasn’t secure at all (like others have also mentioned in this thread). And it depends on the password of course. For example if you use a really secure password (30+ characters), and don’t reuse it, it will in practice be more secure than a short(ish) password and a 2nd factor that allows SMS. Generally 2 factor is used as a term for 2 categorically different athentication methods: one thing you know (password, pin) and one thing you own (phone, physical device/key, or a file works too). The problem is that SMS doesn’t require your phone. It’s incredibly easy to get the SMS without having your phone (even easier with physical proximity) or flat out faking owning your phone number (dpends on a lot of factors how easy or hard that is in practice, doesn’t require physical proximity). Basically, if someone actively targets you and/or that account secured by SMS 2fa, it isn’t overly hard, but it’s good enough at preventing giving access through a data leak for example.
So, back to the security of “solution 2a”: how would someone get access to a long password you don’t use anywhere else, that isn’t written down anywhere (or nowhere accessible), and where you essentially never need to use/access the account in the first place? Nobody would even know that whole account exists unless you specifically tell them, let alone knowing how to get in. Note that this can also be combined with the concept in solution 4, so you’re then using it to only restore a single 2fa code. So that “safety net fallback account” very rarely needs to be updated with a newer Aegis-Backup, making it even more obscure/unknown. That 2fa code then lets you access your normal account and backups, and you restore the full suite of 2fa you need.
It boils down to this: local 2fa with a backup means you need to get access to a single file to securely restore full access to everything. That file can be transmitted insecurely (due to strong cryptography and hopefully a good password not used anywhere else), but I wouldn’t store it out in the open either. On the other hand, any cloud based solution is an inherent black box. You trust them to properly do things, and you only know they didn’t once it’s too late (like Authy). It also means they are, by nature of what they do (storing account access information), a target and if the attacker is successful, you’re the collateral without having been explicitly targeted. Maybe there are sevices out there that let third parties audit their security and publish the results, but I don’t know of any and it would probably increase the price by an prohibitive amount for most people.