If you're using Google Authenticator and rooted your phone, it's not hard to extract the database and transfer the secrets to your new phone. Or you could use an alternative like Authenticator Plus which supports export / import (and has some other nifty features). Of course, both these options come at a cost to your security posture.