It sounds like you want to use hex mapping. Each hex is 3 miles per side, 6 miles across. Whenever the party enters a hex, roll for a random encounter. If they want to explore the hex, roll another random encounter. Make sure your random encounter table has the potential to be nothing. Also, make sure to include non-combat and quest hook encounters as well as dungeon encounters. When coming up with your random encounters, think about the political situation in each hex - is the first hex controlled by goblins, but the third hex controlled by orcs? If so, change the odds of goblins in the first hex to be higher and orcs to be lower, but about the same in the second hex. If the orcs and goblins are at war, there will be different types of goblin encounters - they're likely to be more aggressive toward outsiders and more likely to include warbands. For your hag, does she have any agents in the badlands that might interact with the party? If so, those are encounters - either the party trying to stop them from getting news back to the hag to report on them or her sending her minions after them, a la flying monkeys. What about others who might oppose the hag and might be willing to help the party? Or those who need a favor done before they'll aid the party?

Figure, the party can go 3 hexes per day by road, 4 with a forced march, 2 or 3 over difficult terrain. Roll a survival check (assuming DnD) to avoid getting lost; failure means the party goes a random direction (d6, 1 is the direction they intended to go, 2 is the next direction clockwise, etc.). If they succeed on a subsequent survival check, they realize they are lost and can try to figure out how to get back on track.