Schematic Please

I have to visualize, getting to old.
I would definitely lower the voltage from 13 Volts so as to keep the Arduino regulator cool.
Note: lowest Vin is 7 Volts for the Arduino regulator to work.

I always, always... use Darlington Transistors with built in snubbing diodes, for driving motors.
HFE ~1000

PNP   http://www.redrok.com/PNP_Darlington_TIP127_-100V_-5A_Hfe1000_TO-220.pdf
NPN   http://www.adafruit.com/datasheets/TIP120.pdf         

Just a note; consider using Switch instead of if if if if
http://arduino.cc/en/Reference/SwitchCase
switch (var) {
    case 1:
      //do something when var equals 1
      break;
    case 2:
      //do something when var equals 2
      break;
     etc...   

Also schematic please...

What are you using for the 9 volt source?
10us,  way to fast!!

Relays and Transistors will isolate your Arduino from your motors.

Try the sites here:
http://www.kpsec.freeuk.com/links.htm

As long as there is a ground connection between the power supplies you don't have to connect the Positive outputs together. Therefore you can have 1,2,3,4,5... regulators connected together (as long as there is a common ground)!

[AND]

Some suggestions:
See JPG below.
Since the motor is attached to a threaded rod, you achieve huge power advantages.
This image shows an 20 ohm stepper, in this configuration it easily pushes/pulls 3 pounds (2KG).

http://www.ebay.ca/itm/Nippon-Pulse-Stepper-Motor-6V-PF35T-Uni-Bipolar-/280652253394?pt=LH_DefaultDomain_0&hash=item41582d88d2     AND

http://www.loctite.com/index2.php?cc=ca

Note:

If it is that, you need a new PCB

Try:

These are excellent choices for high current applications:

http://www.adafruit.com/datasheets/TIP120.pdf
http://www.redrok.com/PNP_Darlington_TIP127_-100V_-5A_Hfe1000_TO-220.pdf

Try: