How?
Well, there's many ways they could be pulling it off. The exact way only Yoink has a right to know, unless you manage to defeat them and find evidence supporting one of the ways. Based on what I know it is, it'd entertain me if you pulled that off...
The exact way fits within one of three overall methods though. I will narrow it down by saying it isn't in method #3.
1) They are carrying it, in a similar way that your tribe is currently carrying food supplies. This does have the disadvantage of reducing overland speed and endurance, since 5 months of food (the supplies your own people have) represent some pretty damn significant amount of weight. A common way to pull it off would be to use a Travois, which is simple to make and how your tribe is carrying it's food.
2) They are acquiring it while traveling. Hunting and foraging can be done along trails and still keeping going in a general direction. This requires some element of luck and is a risk, but individual hauling of materials is lessened, so it actually allows faster land travel, allowing time to be taken out to hunt or forage.
3) Trading with natives. If they know where tribes friendly to them are, they only need enough food to the next village and trade goods and they can be sure to travel with very little food.