There is no completely secure way to ensure the server is clean. But there are a few approaches you can take to reduce the risk.
You can reinstall the server. If you know what you are doing, then reinstalling a server remotely is possible. A compromise that survives a reinstall is much harder to pull off than just installing a mostly invisible rootkit would be. So if you perform such a reinstall, your odds improve.
Obviously the reinstall need to be performed using a clean install media. I would use scp to copy the image to the server. If you cannot connect to the server using ssh, then you will have a hard time.
Compare the ssh host key on the server to the public key you see for the server. Some classes of systematic mitm attacks could be revealed this way.
Replace the ssh host key with one that you generated (in case somebody else has a copy of the one that was on the server when you got it).
Use key based logins. If the secret key has been leaked, or if you got the wrong public key in your known hosts mitm attacks would be possible. But some of the mitm attacks which would be made possible by this only works against password based logins and not against key based logins.
If the server has any sort of trusted computing hardware, you might be able to use this to verify the integrity of the installed OS. But this of course cannot give you full protection against scenarios where the hardware itself is compromised.
Things to look out for include the possibility that somebody else has console access to the server as well as the possibility that some of the communication paths inside the server have been bugged (for example a device that passively snoop on SATA communications and can actively inject data during boot would be feasible for a well-funded adversary, and it would be practically impossible to check for remotely.)
Also notice that if you are running on a virtual server, then the host server does have full access to your storage and memory. There is nothing you can do to protect your virtual server if the physical server on which it is hosted has been compromised.
Keep the most sensitive parts of your data away from servers you don't trust. This might mean you have to make it depend on servers you have in other locations for certain tasks. For example for password validation you can probably tolerate the slowdown which would be caused by not letting the server itself see the passwords and instead defer the validation to a server in a trusted location.
