originally I used a 9v batter to power the arduino.
A common PPs 9V battery simply doesn't have enough poke to drive two servos, and you shouldn't be driving the servos off the Arduino's regulator.
Four AAs with a common ground will do a much better job.
I normally budget at least 500mA per servo, more if the servo is heavily loaded or making a lot of rapid movements.