You could use Yubikey with Yubico Authenticator - the secret key is stored in the Yubikey. I did this because phone upgrades were a PITA, as you alluded. If you wanted you could have two Yubikeys (I have my second one in a safe deposit box).