I get a new phone every year, and Google Authenticator sucks for that, but it's by far the second most common 2FA provider. I just got a new phone today, and had to go disable 2FA on all my accounts then re-enable it to generate a new code. SMS is always a good fallback in my experience.