When you say: "they don't quite seem to be producing enough current", that is indeed the problem. But it is also a big understatement 
The AA batteries can supply 0.5A to 2A (it depends on the type and brand). The fan needs 13A !
Could you start with a small fan and a power supply ?
For example a switching power supply of 12V and 2A. And with a fan of 1A.
How do you want to switch the fan ? With a relay or a mosfet ?
Using 12V near an Arduino board could easily destroy the Arduino board. Keep wires with 12V away from the Arduino.
(while I was writing this, JimboZA wrote the same)