The Yubikey can act in HMAC challenge mode, though, but that's not the mode used on the web.

What's inside the cheapest authenticators isn't a private key, after all they present a unique random public key for every single enrolment, so that couldn't work if they held a single private key. Instead it's a symmetric key (e.g. AES-256). Lets see how that's done:

When you enrol at a site, the authenticator mints a completely random new public/private key pair (with Elliptic curve crypto it's really easy to pick random key pairs because with a few bit ops any random bits become a random key) and after signing the enrolment step, the authenticator encrypts its new private key using that secret symmetric key and the DNS name in an authenticated encryption mode and provides that encrypted value too.

The browser, with the authenticator's help, puts together the final enrolment document, with a signature and it includes that encrypted private key as a Unique Identifier. All the Unique Identifiers in the protocol are huge random looking numbers, so the encrypted key blends right in with that.

For a web site, you need to store the public key (obviously) and this unique unique identifier value. You have to do that for everybody, anyway, it's mandatory. You can't decrypt the identifier even if you were sure it's encrypted, you don't know the key, so all you can do is play it back when you want a user to authenticate.

When it's played back, the authenticator takes the web site's DNS name, plus its own secret key, and decrypts the identifier to get back its private key, which it can now use to sign authentication messages. Of course if the DNS name is wrong, the decryption fails, which is exactly the same thing as happens if you try to use the wrong authenticator, or you're being phished, or a dozen other things - the authentication can't succeed.