[magicalhippo]

The login service could send not just the request, but also N random bits for the next session.

These would be stored by the device and combined with the next sessions' request data before signing. The login site does it's own combining before checking the signature.

This way any clone usage would be obvious. If the attacker uses the clone before you, your key wouldn't work for that site anymore. The site could even warn you if it keeps track of previous values.

Likewise it limits the timeframe the attacker can use the clone.

I guess even just 16 bits of data should make it quite resistant to guessing by the attacker.

This requires some non-volatile storage to keep the "future bits", but at 16 bits you can do quite a few logins before having to do a single page erase.

Then again, not my field so perhaps there's something I'm missing.