I lost my SSH key - how do I add a new one?

If you can still connect, add the new public key to ~/.ssh/authorized_keys (or /root/.ssh/authorized_keys). If you're locked out: shut the instance down, detach its boot volume, attach that volume to a new instance as Additional storage, mount it, and add your key to the authorized_keys of the user you log in as. Then unmount it, detach it, and reattach it to the original instance in place of its boot volume. Full walkthrough: Recovering lost SSH access.