When ordering cheap VPS's this is certainly true.
However, the largest cloud service providers are a different matter. If this is a genuine risk, you should look at the likes of Azure and AWS which have very significant certifications for security.
Azure, for example, can offer customer lock keys and provide very significant process security that greatly limits admin access to customer data even without the use of customer keys.
Actually, stealing from a physical server is often easier than the best cloud services. Again using Azure for reference as I am most familiar with that. Azure generally splits customer data across multiple physical storage arrays and even across multiple compute VM's so that physical access to the data centre would not enable access to your data.
Again, though, this is very different to buying a VPS which will be a logical slice of a physical server. In that case, the vendor's admins will have full access to your data whether you like it or not.
All of this comes down to managing risk. What data are you storing? Are you working in a regulated industry (e.g. Finance or Health)? How many records? If you are running a business from a VPS, what insurance do you have? How are you managing your liabilities to your customers?