You have two options,
if you have a system user with a password set (even though SSH Password Auth is off) then you can use the Web Console to access it, as this is like accessing the server physically and thus only supports passwords.
Your other option is the Recovery Kernel (or Recovery Distro, for which you have to ask Support to enable this for you)
The Recovery Kernel you can enable yourself, you can mount your partitions and add your new Public key using this. Use this guide, for how to enable this kernel, the fsck stuff is unrelated: https://www.digitalocean.com/community/tutorials/how-to-recover-from-file-system-corruption-using-fsck-and-a-recovery-iso