Actually, you'd want to remove the compromised client's public keys from the 'authorized_keys' file(s) for any accounts on any machines you care about. Regenerating keys on the server isn't going to do anything useful, aside from generating 'hey, the key for this server changed' messages for any clients that connect to a server with new keys, and happen to have different server keys cached.