No no no guys. Dedicated server is OVER PAYING for this game. If you want your cash to be wasted on cheaters, you can get it.
If not, just search for Rust Legacy server providers. Try some from this list:
http://comparegamehosting.com/pl/game/rust-legacy/ remember to look for FTP / SSH access so you can upload fougerite and edit config. Watch out because these servers are mixed up, some are with experimental only, some with legacy, some with both.
Best is when they give you server for test, so you can check if you are that smart to install fougerite by yourself.
Also VPS up to 40 players may be ok. Most of game servers are on VPS-like services. Just remember to look for guaranteed resources. I was hosting my server on VPS Cloud from OVH, but it's not that affordable. Now I would just buy dedicated rust server from list what I gave you.