your new device is not trusted, so for the first login using that device you must use an alternate to the Authenticator app to authenticate. if your old device still works, you should be able to use it to authorize the new device. otherwise you will need a QR code supplied by your account administrator.
I always setup an alternate phone # and sms account for MFA authentication. of course this must be done before switching to a new device. if the old device still works you should be able to setup an alternate. this is done though your accounts admin site by editing your profile. this will depend on your particular authentication provider.