O seu provedor VPS oferece um 'console virtual' para acessar o servidor? Se sim, use-o!
Caso contrário, você poderá abrir um registro de problema com eles e perguntar se eles podem obter acesso root para corrigir a configuração do sshd. Algo como dpkg-reconfigure openssh-server
.