You have two options. Unfortunately both will require some brief downtime for your droplets.

1.) Create a snapshot of the droplet and re-deploy it. If you power off your droplet, create a snapshot and re-deploy a new droplet from the snapshot you can add your key when the new droplet is created and get access to the new droplet with all your files and configuration in place (but a new IP address).

2.) Open a ticket with our support team. They can reboot your droplet to our Recovery ISO. This is a live Debian environment that will allow you to access your droplet via the console in the control panel, mount your disk and make any needed changes within your filesystem.

I would also recommend setting a root password on your droplet. If you are using key based authentication for SSH this will not change that but the password could be used in the console in the control panel in case of this type of problem. Since the console is considered by your droplet to be a local keyboard and display you can use your password there while only allowing key based authentication for ssh.

What Ryan said! Especially the re-deployed snapshot fix.

We’ve been working on solving the remote key update/rotation issue at Userify. You could actually use it to solve your problem now in the same way that Ryan described (redeploying a snapshot) and just pass in the userify installer as a userdata script (using the CloudInit option in the Userify control panel), and then you can remotely update your authorized_keys file without droplet downtime.

I’d very much appreciate it if when I’m doing a Destroy => Reimage I had the option of adding additional ssh keys… :(

For anyone intend to turn off droplet and take snapshot:
https://www.digitalocean.com/community/questions/how-long-does-snapshot-takes-to-create

The process is damn slow, wtf??? I’ve turned off my production server for 15 mins, it still not finish while I’m writing this comment.