Yes, please don't underestimate the power of changing your workplace. I was stuck at my first school for 6 years without promotion. Constantly C grading. I kept wondering what is it that I didn't do well. My ROs told me I'm doing fine. I got sick of working as hard or even harder than other colleagues and decided NOT to wait here for my first promotion. Took the courage to apply for open posting. Second year in my new school, I got a B. Third year, promotion came. And the rest are all history....

Don't think your promotion is coming just because you spent a great number of years there. If they see your value, it would have came earlier, not later.