Would it by any chance help to condition the input from the speed sensor with a dedicated IC, and then use a faster digital pin on the arduino instead of the analog pin for counting pulses?

http://www.ti.com/lit/ds/symlink/lm1815.pdf

https://www.ebay.com/itm/1-PCS-LM181...from=R40&rt=nc