I use Authenticator Plus (https://play.google.com/store/apps/details?id=com.mufri.auth...) which has encrypted cloud backup (Google Drive or Dropbox). The encryption is done client-side. When I get a new phone, all I do is set up A+'s cloud sync on the new phone, enter the passphrase I've used previously, and it syncs all my TOTP codes.

As a bonus, the backup is just an encrypted sqlite DB (with dirt-simple schema), so you're not tied to some inscrutable proprietary format, and can easily extract the tokens if you want to use a different app/service.