With that size battery, about 10 minutes is all you can expect for it to last. It's not that the battery isn't holding its charge, you are using the charge up. If your speed control is capable of handling a lipo, and you can afford a lipo and a charger, then I would get a Gens Ace Lipo (can be had for around $20... Sky Lipo or Blue Lipo will work just as well for playing around and are cheaper) and a lipo charger that will charger around 5amps (Thunder Charger or similar cheap lipo charger).
With a 5 amp charger and 2 batteries, I think you'd be more than pleased, especially compared to what you have now. You can recharger one battery while you run the other. Should get runtimes of 20 minutes or more depending on how you are running the car.
If you need to stick with NIMH or NICD, check these out. That way you already have a charger to charge them if you don't have a lipo charger.