@ftl This is, unfortunately, one of those times where "It depends" is actually the best answer. As the GM, you will have to look at what's going on in the campaign, weigh what your party enjoys, and then find the best path forward. Sometimes you'll have to look at how much time you have in a particular session and what the party is trying to accomplish and then add or skip random encounters accordingly.
The easy mode is to just have folks roll for each day of travel, or night at camp, or hex on the map. But overall the best way for those open exploration style parts of a campaign is to have a GM that looks at whats going on and tailors to it accordingly.