It is tough to harass a sedna with priest minions. I think the best solution is to attempt to negate a heal with foul grasp. It is not EASY to do, but it is amazingly effective, doing an additional pseudo damage = to however much she would have healed, + potentially more spit damage.
As has been mentioned, auto attack and Ooze are your best friends against sedna, since she cannot directly counter them. Slayers wraps and max Ooze will help you dish out the damage, and prevent her from returning it well. Crits can also mess up her healing math, sometimes letting you get a kill when she isn't expecting it.
Ultimately though, it all comes down to how well you use foul grasp. Once you spit + engage, do not immediately foul grasp. Instead start auto attacking her, and then select foul grasp, but do not USE it on her yet, just make sure your cursor is ready. As soon as she starts the heal animation (Often recognizeable as 'not the attack animate') grab her. Disrupting the heal resets the cooldown, in addition to preventing a dispel (heal 3).