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.

One possible short-term fix to this situation is to use some config management tool (ansible may be a good bet here).

You could notably use the authorized_key module (https://docs.ansible.com/ansible/authorized_key_module.html) to remove one (or more) specific public key fingerprint from a given user's authorized_key file.

An example is lacking for your needs, but something like this could work:

- name: Set authorized key took from url
  authorized_key:
    user: charlie
    state: absent
    key: https://github.com/charlie.keys

You can also (in ansible at least) run a command to create a list of all users on a system, by querying /etc/passwd.

You could also just create a fresh whitelist of keys and remove everything else, but that may not be practical in your situation.

The ansible docs give a rough example of how that could work:

- name: Set authorized key, removing all the authorized key already set
  authorized_key:
    user: root
    key: '{{ item }}'
    state: present
    exclusive: True
  with_file:
    - public_keys/doe-jane

In the long run, you may want to consider having jumphosts - I've found teleport to be rather good.