So it seems to me that the keyword stealth is just one of those things they throw onto a character they want to be more interesting. Stealth is an extremely powerful ability. Any character you play who has stealth is effectively TWO characters. In combat that character adds their own strength PLUS removes the strength of another (usually the most powerful) potential defender on the opponent's side. Now if the character with stealth were to stand and attack again, the number of characters it counts as effectively multiplies and gets silly. On top of that, the ways to counter stealth are few and far between (Hodor or Ser Arthur Dayne) with the only reliable way being to have stealth as well. Deadly is another powerfull keyword but it doesn't stack. If you have say three deadly characters, still only one defender dies from them. Stealth stacks, however. 3 stealthers means three attackers and three defenders who are useless. A net gain of six for the price of three.
So in conclusion, I think this game could really use more counters to stealth. Or perhaps rethinking the average cost that should be given to a character with stealth. I'd say a 2 strength stealther should be at least 3 or even 4 cost.