Qual versão do sshd você está usando? O OpenSSH 5.4 aparentemente tem uma opção de revogação de chave:
* 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.
Se você estiver usando uma versão anterior, provavelmente precisará executar todos os arquivos authorized_keys possíveis em todos os servidores para procurar e remover a chave pública suspeita. Isso incluiria qualquer conta em que o User-A pudesse ssh, incluindo o root. Isso pressupõe que você não está usando o gerenciamento centralizado de authoried_key.