1. Login to https://mysignins.microsoft.com/security-info
2. Since you have lost your Okta verification, you need to choose "Sign in another way".
3. Select Option "Text", use the registered cellphone to collect the SMS verification code.
4. Fill in the code and sign in.
5. Delete the old Authenticator app or old Phone.
6. Add a new sign-in method and select "Authenticator app" or "Phone" to reset your MFA verification mehods. Please refer to this User guide for "MFA registration"details.