But, recently I have switched to a new phone and eventually I lost my 2FA Google Authenticator Backup code and I am not able to log in into my account anymore.
This is a terrible problem with Google Authenticator. If you lose your phone, it is over and there is nothing you can do.
The best thing is to use an alternative com Google Authenticator. You can use Authy app. This is a very nice software, which let you save all your 2FA codes in your account.
Authy has an option to prohibit the registration of new devices. So if someone steals your Authy password, they can not add an additional device, unless if an authorized device allows the registration of new devices to your account.
I made a post about it here: https://bitcointalk.org/index.php?topic=3178131.0
I think you should consider using Authy in your new phone.
Definitely, I would be definitely move out Google and use your suggestion but right now the priority is to get back the Cex account
