Should you drive all 25 leds continuously at full power, they'll draw a current of 25 x 60 = 1500 milliAmperes, or 1.5 amperes an hour.
Quite a lot of NIMH-AA batteries can deliver up to 2700-3000 milliamperes. The arduino itself does take a few mA as well, but that's probably not worth counting.
I think this is confusion between current and capacity. A batteries capacity is measured in mAh or Ah, which is really a measure of charge, not current. A 2700mA hour NiMH AA cell can provide 270mA for 10h (capacities are usually quoted at the 'ten hour rate' - run down a battery really hard and its capacity is reduced (and it may be damaged permanently). It does not follow it can provide 2.7A for 1 hour. It does not follow that it can provide 2.7A at all (it probably can, but at reduced voltage and generating a lot of heat in its internal resistance).
For completeness 1mAh = 3.6C (coulombs - one amp for one second = one coulomb)
Also good luck finding a battery holder that can take that sort of current - cheap ones use rivets and steel springs and can both lose a lot of voltage and be unreliable at high currents. There are more expensive rechargeable cells with solder tags and proper data sheets for industrial use - might be worth considering.