Well it depends on your hoster but most of them grant you remote access to the system like ssh serial console, kvm console, remote-console, vnc ...... try to figgure out if your hoster allow this and log into your system and fix the key issue
Take into consider to tell the community which OS you have, perhaps someone has another Idea.
I assume you allready checked the firewall that ssh access is allowed. How it looks like when you try to connect to your system is something in your terminal window like a connection/error message?, maybe a screenshot would be helpfull