I would suggest you ask your provider. They offer a possibility. For example, a rescue function. Also, you can booting an emergency system in a virtual environment.
No, this can only be done from booting a server by a rescue system, e.g. by a network boot procedure. From there the SSH key information needs to be replaced manually on disk.