Honestly that's a lot of work. I've been using Google Authenticator for 2 years now with 7 accounts. Everytime I change phones (twice now) it's been a nightmare. Also since I travel, half the time they don't work.
I am going to build Google Auth support into Authy and it will be 10 times better that the Google Authenticator App....how I wish Google would do it, but they have abandoned Google Authenticator long time ago (they didn't even bother to support retina display's).
Backup codes. It's not the cleanest approach in the world, but it's still an actual second authentication factor.
How can you safely disable Authy if you lose your phone without risking someone else having the same ability to do so? This is a solved problem.
I agree that the process of switching phones sucks, but it almost needs to in order to keep the MFA keys difficult to clone.