Problem they had was that ssh doesn't really have any way to enforce details of how the client key manifests and behaves. They could ship out the authentication devices after the security team trusted the public key, but that was more than they would have been willing to deal with.

Rotating the passphrase in the key wouldn't do any good anyway. If an attacker got a hold of your encrypted key to start guessing the passphrase, that instance of the key will never know that another copy has a passphrase change.