Had to use another microsoft account just to be able to post this because I cannot log in to my account.
I changed phone and the Authenticator app needs the Authenticator app to authenticate... The only methods to authenticate are "Approve a request on Microsoft AUthenticator App" or "Use a verification code", which both uses the app.
Somehow, even after reinstallation my account is listed on the Authenticator app, but it just does not receive any notifications. I reinstalled mutliple times, restarted the phone, made sure notifications are enabled etc but still nothing.
I am told to use https://aka.ms/mfasetup but for this you need to log in.
I have a recovery email but no option to receive a code this way for some reason. It is valid as I managed to change password.