About every 2¼ years, if I think back. I moved to Sweden ~9 years ago and in my time here I have owned 4 different phones, in order:
1. Samsung flip-phone.
2. Sony Ericsson Walkman W890i. The best phone I ever owned.
3. Nokia 206. A somewhat worthy replacement of my broken W890i, but by this time it quickly showed that a university student needs a full browser in their pocket.
4. Motorola Moto G (2nd gen). My current phone. A pretty solid phone without breaking your budget completely. Does what I need it to do.