Security when SSH private keys are lost

What version of sshd are you using? OpenSSH 5.4 apparently has a key revocation option:

* Add the ability to revoke keys in sshd(8) and ssh(1). User keys may
be revoked using a new sshd_config(5) option "RevokedKeys". Host keys 
are revoked through known_hosts (details in the sshd(8) man page).   
Revoked keys cannot be used for user or host authentication and will  
trigger a warning if used.

If you're using an earlier version, you probably have to run through all possible authorized_keys files on all your servers to look for and remove the suspect public key. This would include any account User-A could ssh into, including root. This assumes you are not using centralized authoried_key management.