Jednoduše. Na nový telefon si nainstaluješ google autentifikator a ze zalohy naskenuješ čárový kód, který sis při nastavení 2F autentizace do autentifikátoru vyexportoval.
Pokud jej nemáš, pak kontaktovat podporu obou služeb a zkusit je přesvědčit, že nehodláš účty ukrást (tím tě neobvňuju, pouze objasňuji pohled podpory)