crikey
you are probably burning more power in the on board voltage regulator than anywhere else!
can you use a 6 volt battery (I recall seeing 6 volt lead acid somewhere)
either that or a more efficient (switching) voltage reulator to provide 5 volts for the 'duino
or even 3.3 if you can get away with that