If you set up your VPS with a hierarchical deterministic wallet[1] or a passphrase-protected private key[2], your hosting provider will be unable to determine your private key.
There's really no getting around the evil maid attack[1], if someone can attack your hardware directly. There's even evidence that a sufficiently clever attack can persist through formatting and re-installing a drive[2] - note, people have also found exploits in network firmware... remotely exploitable exploits. If you can do it by accident[3], then most likely it can be done with malice aforethought.
Edit: adding a strong pass-phrase /does/ give you a significant level of protection; While it doesn't offer protection from an evil maid type attack (where the attacker trojans your server, then you decrypt your key after said server was compromised) it does offer quite a bit of protection, say, from an attacker who has access to old backups but not your production system. So I think a passphrase on all of your important private keys is a worthwhile thing to have.
I just want to make it clear, once you decrypt that key from within a compromised system? all bets are off.
Edit: adding a strong pass-phrase /does/ give you a significant level of protection; While it doesn't offer protection from an evil maid type attack (where the attacker trojans your server, then you decrypt your key after said server was compromised) it does offer quite a bit of protection, say, from an attacker who has access to old backups but not your production system. So I think a passphrase on all of your important private keys is a worthwhile thing to have.
I just want to make it clear, once you decrypt that key from within a compromised system? all bets are off.
[1]https://www.schneier.com/blog/archives/2009/10/evil_maid_att...
[2]https://news.ycombinator.com/item?id=6148347 (of course, this specific attack wasn't as scary as it could have been, say if the same sort of thing was remotely accessible)
[3]http://theinvisiblethings.blogspot.com/2010/04/remotely-atta...