It has an export function that you can scan from an old phone. And I kept the setup keys in my keepass database.

On top of that now Google backs those up for you too.