Some time passed, phone broke, and I went to Apple store to get a new one. They needed to adjust some stuff on "Find My" so they had me log into my account on one of their laptops in store. All I needed was my password... no security key.
How could this be? I just confirmed again that it is needed by going through the same journey at home on a personal device - security key needed to log into iCloud.
I must be missing something.