Your "power supply"is a battery. Those 9Ah batteries can output quite a lot of current so I would say that's plenty.
And yes, you can connect it straight to the Arduino if you don't load down the 5V output of the Arduino with stuff you might not mentioned. And for the motors, speed will change a bi depending on the charge of the battery.
@juma_yetu, first point, read better 
Second, those lead acid batteries happily do 1C which is plenty.