You can either catch an Elgyem repeatedly (not the fastest, yet faster than Munna :P) with the nature desired, or for the more patient, here's what to do.
Catch Eevees and evolve them into Espeon. Espeon is fast** and have the synchronize ability. I'm not sure it's the fastest, though.
I hope this helps.