More Ah will just last longer, and since you don't need much, it seems like the primary consideration should be size or weight. Separately, though, I think this 12V battery->inverter->AC adapter route is quite awkward. You can probably get by with just using AA batteries. You could either set up your own battery holder or get some AA to C battery adapters, which are just sleeves or shells that fit around AA batteries to make the final diameter match that of C batteries.
You start out ok, up through where you got the 20 mA, but then you got sloppy with the units in exactly the way this blog post was supposed to help people avoid. 20 mA is already a rate, and as long as that fan is running, the current is 20 mA, and it is wrong to say 20 mA per hour or 10 mA for 30 minutes. It would be correct to say the battery will deliver 10 mAh in 30 minutes.
I've crossed out the incorrect parts in your comment in the hopes that it will help others avoid this kind of mistake. The 65 hour result based on the starting assumptions is right, though.
As a rough approximation (within a factor of two), I would expect similar battery life. The main thing I'm skeptical about is that 5V is not a natural voltage for a lithium ion battery. If there's actually a 3.7 V, 2600 mAh battery inside and the converter to 5V is 90% efficient, you'd be getting the equivalent of about 5V, 1750mAh.
I don't know enough about your system to know for sure. There's got to be some limit on your alternator and whatever battery charging circuit is in your car, and while my impression is that lead acid batteries are among the more forgiving regarding charging, you still might limit their life or otherwise damage them if you just do what you are proposing.
I am concerned that with the level of electronics understanding you have presented, you might be risking damaging or destroying some fairly expensive equipment. It seems like you might be better off looking for some pre-made solution, like a general-purpose external/backup battery for phones or other electronics.
On to your specific case. First off, you should realize that with four batteries instead of the built-in two, you will get at most 2x the battery life. You should not put your batteries in parallel, and if you just put all your batteries in parallel, you would only have the 1.2V individual battery voltage anyway. You should also go through a regulator, too, to make sure you actually give your device the 5V it is expecting since the fully charged batteries might be 5.5V or more and damage the device, and they might get too low as they discharge. Something like this step-up/step-down regulator could work:
With that regulator, it would be better to go with 6 AA batteries if you have the room for it. But, if you go down this path, make sure you get a better understanding of what you are doing and that you are ready for the consequences if you make a mistake.
I don't know what that 12A/5h notation indicates. My first guess is that it's a typo or other mistake; my second one is that it's 12Ah at a five hour discharge rate. If the batteries weigh about the same and have similar dimensions, their capacities will be similar.
"How many mAh a battery will last" is not a good question formulation because it sounds like you want to know how long a battery will last just based on its capacity. It's like asking how many days until you need to refuel your car that has a 12-gallon gas tank without saying anything about how much you drive per day.
As I said in the 9V alkaline battery example, you're basically going to get about the same amount of energy per weight for any given battery chemistry, so since a 9V weighs about the same as a AA, it's going to have about the same amount of energy, and since energy is measured in Wh, which is Ah times V, a 9V battery will have about six times lower mAh rating than a 1.5V battery of the same weight. If you happen to know your application for the 9V draws the same current as a specific application for AA or AAA, then yeah, it will not last as long, but that kind of situation is rare since there aren't many products that can run from either 9V or 1.5V.
I am happy to hear you have had good experiences with us. Lynxmotion has sentimental value for me since I played with some of their earliest arms and hexapods almost 20 years ago, but I have not really kept up with their more recent offerings. Is there something you see RobotShop actively doing to hurt Lynxmotion? My impression was that Lynxmotion was mostly the effort of its founder and that he retired; if that's the case, RobotShop would be saving it from disappearing completely rather than causing a problem. But I have no inside information and have not even paid attention to public information about it, so for all I know, all the original Lynxmotion folks could still be active in the company and butting heads with their new parent company.
I would like to offer more of the servo-based parts and kits you are asking about, but there is nothing specific in the works, so it's unlikely that we would have anything new for at least the next few months. We might start with something basic like small grippers; for bigger, more complicated systems, it's not clear to me that general-purpose RC servos are the way to go. Something like the Robotis/Bioloid products, with specialized (and proprietary) servos offer a lot more for robotics. How do you think these newer systems compare to the Lynxmotion type of products?