As mozz said, DigitalOcean is a good company, but looking for that much storage you would be spending upwards of $100/mo.
And if you are running anything illegal, you will likely have your instance investigated and have your ssh keys and password overwritten by whoever is hosting it.
If you are looking for something that is as private as possible, you would be looking for a bulletproof host, which will cost significantly more.
Assuming you aren't looking to run anything illegal, I also provide hosting, and you can reach out to me if interested.