You need to generate a new key pair (private/public keys) and then add your public key to your server so you can connect using the new keys.
Here you have a guide that can be very useful:
Once you can connect to your server using the new keys, remove the old key from the authorized_keys on the server.
Was my answer helpful? Click on