Ein Timer (Timer1) müßte schnell genug sein, AFAIR geht seine Eingangsfrequenz bis clk/4 (4MHz). Die Frequenz hängt natürlich von der Drehzahl ab, Du mußt schon selbst wissen, womit Du den Sensor betreibst.
Statt Operationsverstärker würde ich einen Komparator verwenden, der ist für hohe Geschwindigkeit gebaut.