I don't think the Advanced Data Protection is relevant either, but I'm not certain since by turning it on Apple says I'm on my own for recovery now (account recovery is turned off). That might enable device passcode authentication, but again, I'm not certain how all of these settings interplay.
When I add the YubiKeys, it does not turn off my recovery key. And I don't think it should, at least not without letting me know. Turning off the recovery key usually reverts to trusted device authentication using the six-digit codes.
I think the recovery key option, which allows account recovery using the 28-character key or the device passcode, might be the difference here.