Wouldn't it be trivial, yet highly useful to have a key-rollover feature in the ssh client?
The client could detect that it's using a defective key and generate a new one, while stashing
away the old, compromised key.
When the user tries to log in the ssh client could then try the new key first and fall back to
the old key.
When logged in the client could then remove the old key from authorized_keys and insert the
This would save a lot of manual work and what's more important: It would eventually get rid of
all the compromised keys, even on poorly maintained systems (where the server doesn't
blacklist) where the user is less than diligent about changing his keys.