The key will be in ~/.ssh/authorized_keys
You can delete the line for the old key with the editor of your choice.
You can generate a new private key by running the following command on a client machine.
ssh-keygen
Depending on which algorithm was used add the contents of the ~/.ssh/id*.pub file to the ~/.authorized_keys file on the server. It will be a single line
It is probably called:
id_rsa.pub
And the key will look like
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAIZ5CYnbANePH8y1rKvFIpWNWrr3kSuelNP61W/yPiPtf11DZgdWsP5eaBQQqEZpXnw57pu5SuPHe5FPn+L39c/xtPJdvn1ZSVo1OTWMPkKGX+5WuL5ypaHN5J2E4qkZD9vzQ4OcUGGdODZ676TPV5cAD7oYHvBWKdCxPUztUAAAADAQABAAIZ5CYnbANePH8y1rKvFIpWNWrr3kSuelNP6 user@foo
Note that it is a single line. If you delete the authorized_keys file on the server you will need to make sure the permissions are correct.
chmod 0644 ~/.ssh/authorized_keys