Na'asiyah has always been a favourite of mine, and I've already built several decks with her. Not only does she have a brilliant backstory, her innate ability makes her both a strong attacker and defender right out of the box, and her low-threat is a nice addition.
Her only drawback is and has always been that you can't pay for allies with her resources. Well duh - enter Forth, The Three Hunters!, which legitimizes building a deck without any allies at all. The cost reduction of this contract also synergizes with the strategy to save up Na'asiyah's resources for more important things. And once you flip to side B and add Golden Belt she can wield up to 4 pieces of equipment making her a true combat-monster.
Speaking of monsters: Beregond will also be quite happy about some extra toys, most of them being free for him.
As with other decks in this style, this should be paired with a partner-deck that can handle most of the questing (even though Éowyn will do her best to help) and possibly deal with nasty treacheries, i.e. a spirit-based deck which can provide some copies of Unexpected Courage for Beregond, or a Leadership-deck which has Armored Destrier at hand.