Sure you can. Main waypoints for Linux VPS are: create a Linux user for every masternode, set a port for outside connection with other desire nodes, assign dedicated ip address for that external port.

The main parameter of VPS provider that you should look for is a possibility of multiple white ip addresses allocation for one instance(Linux VPS).
I can say for sure, that Amazon in there AWS cloud have such possibilty. Not sure about Vultr and Digital Ocean, but they can have it too. Arubacloud provide that option but set up is difficult and expensive.

But several reasons exists for NOT to do that construct with multiple masternodes on one VPS, and one is very high RAM and disk space usage.

As an option - try to use arubacloud vps for every masternode by minimal price - it's about 3EUR per month now.