I am interested in advancing an Efreeti to 16 HD and thus making it huge. My question is about advancing a monster with spell-like abilities. Would the caster level - currently 12 - increase by advancing said monster?
When a creature's spell-like abilities are listed as used at a specific caster level--such as 12 in the efreeti's case--that caster level is fixed and usually unaffected by changes in Hit Dice or the addition of templates and class levels.1
If a creature's spell-like abilities lack a specified caster level, the caster level for those spell-like abilities is the creature's Hit Dice.
As with everything in D&D 3.5, there are always exceptions. For example, from page 44 of Dungeon #116 there's this feat:
Your spell-like abilities are more powerful.
Prerequisite: Spellcraft 4 ranks, spell-like abilities.
Benefit: Your caster level for you spell-like abilities increases by +4. Ths can’t increase your caster level for your spell-like abilities beyond your Hit Dice. However, even if you can’t benefit from the full bonus immediately, if you later gain non-caster-level Hit Dice you may be able to apply the rest of the bonus.
If you have spellcasting ability from multiple sources (from gained templates or from a character class) you must choose which set of spell-like abilities gain the feat’s effect.
This does not affect how often you can use your spell-like abilities in a day. It only increases your caster level, which would help you penetrate spell resistance, increase the duration and damage of some spells, and so on.
Special: You may select this feat multiple times. Each time you choose it, you must apply it to a different set of spell-like abilities.
Increasing CL Without Houseruling It:
(Savage Species, p. 39)
You convert a spell-like ability to a supernatural ability.
Innate spell-like ability,
One of your innate spell-like abilities becomes a supernatural ability. It is no longer subject to spell resistance, though it can still be suppressed in an anti-magic field. Using this ability does not provoke an attack of opportunity. The number of uses, if limited, does not change. The effective caster level equals your total Hit Dice or the effective caster level of the original ability, whichever is higher.
You can gain this feat multiple times. Its effects do not stack. Each time you take it, it applies to a new spell-like ability.
By strict RAW, no, the caster level of the spell-like abilities does not change, and their save DCs will change only according to any change in the relevant ability score.
However, following this rule will mean that any offensive SLAs will rapidly become irrelevant, as they become too easy to resist to ever land on CR-appropriate enemies. I thus recommend that you increase caster level by the same number that the CR increases by, and that you increase save DCs by no more than half, and no less than a third, rounded down, of the increase in CR.