Thinking further, I might be more inclined to simply add supply loss text in to more exploration challenges. This system feels a bit too 1 size fits all, which is probably where that sense of taxation comes in.
I can think of 3 places I'd work it in: a penalty on failure for exploration challenges more broadly, as a cost to make a skill roll for some possible exploration challenge solutions, and in some cases, as an alternative to rolling altogether.
If we had the luxury of starting over altogether, I think I would work Supply as a currency into the knack system as well. That would encourage players to find ways to use those abilities to resolve exploration challenges without paying other costs, and you could have a whole section on ways to alter Supply refreshes for things like urban campaigns.