I think every few months is the norm, i only change mine if one breaks and usually only the one that break if iv got one, if not swap the full set.
If you keep replacing the strings tha will be why it goes out of tune quickly, just try and be patient and keep tuning it up eventually it will all settle in n be alot more stable, most guitar strings stretch a little from new.
The other thing that could be effecting the tuning stability is the bridge, if its a tremelo then tightening up the springs in the back or adding more may help.