Hi Chems,
Take a look at: AccelStepper: AccelStepper library for Arduino Which is a stepper library that will let you ramp up speed. Many people have found this greatly increases their maximum speed.
Remember you need to ramp DOWN too; or lose steps...