Acho que seria mais fácil e você teria mais sorte em encontrar uma solução que remova os usuários da lista de usuários, ao tentar remover as chaves ssh.
Ao remover o usuário, você está revogando o acesso desse usuário à máquina. Você está em uma situação em que isso não é possível? Se não, um script como o seguinte pode ser usado para remover facilmente usuários de todas as suas máquinas
#!/bin/bash
ssh -t user@host 'sudo userdel -r badusername'
ssh -t user@host2 'sudo userdel -r badusername'
O -r no userdel removerá o diretório pessoal do usuário, o que significa que a chave também será removida.