You can use Authy, the restore feature works great. You simply have to save the recovery key somewhere safe. You also have to thrust the developer here (Twilio) in this case.
What I don't like about Authy is that it requires a phone number (and verification of the number) to use it. That's one more point of failure, depending on the situation. I prefer not to link a phone number with services unless it's unavoidable.