AnalogRead too slow... Faster alternative?
Ignacio's proposal is surely a good one if you really need higher sample rates, but I would try another approach: 
Average your signal before sampling it! This can be done by connecting a simple RC lowpass to your AD input. 
With that you get rid off those high frequency noise you don't need, but without wasting CPU time.