Well, Horsea is always found at Level 25, therefore it would take eight levels for it to evolve.
You have the Super Rod therefore you have past Route 15, which has Pokemon approaching Level 40. Realistically, training your Horsea eight levels here should not take that long. You can put the Exp. Share on Horsea and see how much it gains in a battle; if you feel it will gain eight levels quickly, do it. It's entirely your judgement.
This all being said, the amount of time it took you to find a Seadra is peculiar. When you are using your Super Rod, are you encountering Relicanth and Clawitzer/Dragalge? If you aren't, then you're either not in Ambrette or not using a Super Rod. :P If you are, then you have awful luck. Congratulations! ~
Good luck on your Seadra search!
Hope I helped. :)
Source: Serebii + Experience