I’m relatively new, so there’s probably better/more elegant solutions somewhere, but here’s my best guess.
Do you still have the .pub file from when you created the SSH key you no longer want? If so, and if you can view the contents, have that available.
Then, SSH into the server and type:
cd ~/.ssh
In that folder, you should have a file called authorized_keys
Use your favorite editor to remove the SSH key that matches the .pub file you have open.
I just tried it on a droplet that I spun up, and it seemed to work. When I tried SSHing in with the key that I deleted, I got the “Permission denied (publickey).” error.
Please reply if this works for you. If so it’ll be my first answer on the forum here!
EDIT: I totally misread your question. You wanted to replace the SSH key, not just remove the old key.
So the same basic principle applies: You need to edit the authorizedkeys file with the SSH keys that you want to log in. So the only additional step is to, while you are logged into the server and editing the authorizedkeys file, paste in the contents of the .pub file for your new SSH key.
Again, please reply whether this helps or not.