Consultation regarding Linux VPS

Hello, So the situation is like this: today I could not login to one of my VPS servers using SSH keys authentication. The error I was getting was "Server refused our key". When prompted for password I was getting "Access denied" after entering right password. I wrote to VPS support to change the password. When they did it I could not login either with new password. Then they replied me that "It looks like you have changed your password manually with "passwd" and deleted root user. Now you can login". And yes after this message I could login. Even with SSH key. I have not done anything with configuration of this VPS for weeks. I don't remember changing the password with "passwd" recently. I have checked /root/.ssh/ directory and there were no new ssh keys added. I have viewed /root/.bash_history for an suspicious commands and I did not see any. So I am looking for short consultation with experienced Linux sysadmin, who could answer these questions: - How to check if there was any suspicious activities done with this VPS? - What commands you would recommend me to use (and what outputs to expect) to check was it hacked or this issue was other type? - Is it secure to use this VPS in the future? What would be your recommendations? Thank you in advance!