I use Aegis Authenticator on Android which does encrypted cloud backups, so changing phones isn't much of a problem.

I also only keep critical accounts there, the rest goes into Bitwarden. I realize this isn't as secure, but with those accounts I wouldn't even bother with 2FA otherwise.