Doesn't need to be a combat monster but should be small and stealthy and fly.

Possibly the Flying Leaf-Tail from Nexus of Power? It is a Minion so it should to be statted out as a Rival if you want it for a companion, but it has some natural camouflage ability—no actual Stealth skill, but that could be written into the Rival stats.

Or what about this guy?

http://starwars.wikia.com/wiki/Ral_(creature)