User deleted Microsoft Authenticator

Question

One of our users bought a new phone over the weekend and deleted his old phone before setting up Microsoft Authenticator on the new phone. Now he cant access the security page on accounts.micorsoft.com to add his new phone because it sends the code to the old phone thats now been wiped clean.

I restored his old phone (Iphone 14) but authenticator did not restore. I turned off MFA on his account so he can access our network and Office products but we are implementing MFA on January 1st 2025.