Game stagnates if supply card not drawn
First of all, yes. This is something that I have noticed happens sometimes in the game. I don't think it happens all that much, but it is definitely noticeable when by round 3 there has not been any supply yet. 

I don't think this is a problem. Think about if no Clash of Kings would ever happen? Or if no Wildlings ever attacked? There are many such opportunities for the game to be "lacking" in something. I think it is part of the dynamic nature of the game. It does not require any of those things to happen, but if they do then it makes it interesting, but it also makes it interesting if it doesn't happen.

Saying that the game "stagnates" implies to me that you may not be playing the game entirely correct. Most of the times when I play the game, I barely have any armies with more than 1 soldier until mid-game. Since I rely on support and taking larger territories and having more actions. 

It really depends also on what optional rules you are using. The tides of battle cards make supply less relevant, since the size of the army is not the most important factor. If you are using the rule where the seasonal cards are set out such that you can see the next 3 cards coming up that will also impact the game, you will know when a supply is coming, or if one is not coming and be able to play accordingly.

I would not say that this is a problem with the game, maybe only a problem with expectations. I do not think any house rule needs to be made for this. There are enough ways to "solve" this problem. Most of them come from your own strategy.