Instead of using the little heat generators, er, I mean linear voltage regulator, on the board, go with an off board switching regulator.They take in the higher voltage and efficiently convert it to 5V with very little battery power thrown away as heat.
See if you can locate this or something comparable at Farnell or your favorite source, and power your Arduino thru the 5V pin instead of thru the regulator.