Another idea: Keep the permanent camp, but get rid of all fast travel and teleportation. If you want to long rest, you have to walk to camp. The current system feels ridiculous because there is no cost to or restriction on the character or the player. If the player has to walk the character all the way across the world every time they want to sleep, they're going to have to learn to be more efficient with their resources or spend a ton of time walking the same paths over and over.
I don't particularly like this idea. I hate the permanent camp, but having to walk there every night replaces something unreasonable with something else that's unreasonable. I also don't like punishing everyone in order to discourage a particular behavior. But maybe there's a nugget there that we can use.
I totally disagree with the need to walk to camp. It is just a waste of time for the sake of wasting time. Should there be a risk involved in going to camp? Absolutely. But there is no difference between integrating a random roll on engagement fast traveling to camp, than to do it where you camp on location. There is literally no difference at all. Basically what you are requesting, is people play the way you want them to, or else be penalized, have your game time either limited or wasted walking through complete zones for camp. Good luck getting that implemented.