Same issue here in the UK since updating to IOS18, but only on my works phone (iPhone XR), working fine with my personal 15Pro.
Tried the first option, nothing happened, I've switched of the notification in the app within system for now, it cleared, cam back when I turned it back on, therefore switching off for now. Going to see if I still get an app notification tomorrow when I log back in to my works laptop and prompted to authenticate.
I spoke to our IT team and they said to try swiping down from top of page you will see a notification for Authenticator delete it, mine wasn't showing any, perhaps it might work for you guys.
Good luck