I think the simplest and best way to approach the rest issue is simply to attatch long rests to having food. Make it so that you either need to have food in your inventory, or be at some kind of home base or inn before you can long rest. That's what Pathfinder: Kingmaker did and that worked without issue. This lets them make short rests more useful and makes it so (provided they limit food more) players can't just spam long rests whenever they feel like it while not making it entirely punishing to not have food since you'll still be able to fall back to camp, it just requires you retraversing the map.
