I felt this was best answered by examples. A lot of examples :P
"Sudden" does not guarantee surprising
This is fundamental "show, don't tell" - describing something as being "sudden" doesn't mean the reader gets a sense of surprise while reading it, any more than you'd laugh at reading the line "Bob is a really funny guy." So one key skill is, look out for writing "surprises" that aren't surprising. Here are a few examples:
Suddenly, the train arrived.
In most cases, this makes no sense. A train can't arrive "suddenly" - you can see it drawing near; it makes a lot of noise; clocks everywhere count down to its arrival. Describing this as "sudden" is either an artificial attempt to make an ordinary event seem more exciting, or else it's trying to explain something else - e.g., that the protagonist's attention was elsewhere up until now - and doing so poorly.
Suddenly, the patient's heart stopped beating.
This makes sense intuitively, but in practice it's a mess - it tells us what happened, but it doesn't convey the actual experience. That's because the protagonists don't experience it as "suddenly, his heart stopped beating" - instead, their attention is on the blaring alarms, or the patient's sudden collapse, or the steady thump falling silent. In order to convey the experience of suddenness, you need to convey what the protagonist is actually experiencing.
Suddenly, the door opened.
This makes sense, and can work. Using "suddenly" gives an air of surprise and tension. But if that's not backed up by other elements reinforcing that atmosphere, you risk the "show, don't tell" dangers I mentioned above. Particularly, overusing this casual "suddenly" is what can really grate on a reader - the more you use it without clear justification, and the more you rely on it to create excitement without doing other things to help, the more obvious and artificial it seems.
Suddenly, Claire screamed and ran from the room.
This is the good example. Why does this work where the others don't? Because here, it's a sudden action, and the suddenness of it is what surprises us. If the surprise is amply clear, you can safely use "suddenly."
Back it up
If you are using "suddenly" for surprise effect, it's good to back it up with appropriate portrayal of the event. Compare:
Suddenly, the butler came in with the main course. It was a delicious lasagna with fresh greens and spices I didn't even recognize.
Suddenly, our conversation was overpowered by bustling servants clearing the table in preparation for the next course. I managed to snatch one last mouthful from my plate before it was whisked away, and before I had swallowed, the butler was proudly uncovering the next steaming dish.
With the second, the "suddenly" element is clear, and fits in just fine with the rest of the paragraph. In the first, it is perhaps not implausible, but feels out of place.
Surprise does not require suddenness
"Luke," he suddenly said, "I am your father!"
There's an intuitive sense to this example: learning such a revelation provokes lots of immediate, sudden reactions. So isn't this sudden?
No, of course not. The reactions are sudden; those you leave to the reader (and, I guess, to Luke). The action itself isn't sudden. It doesn't rely on suddenness to be surprising. Even if the action is sudden, that suddenness isn't what's important, and will be more distracting than helpful.
Similarly, if something surprising happens, it might happen quite un-suddenly (like a magician, milking the trick's punchline for all it's worth), or its suddenness may be irrelevant. Convey the scene as best you can; make sure the surprise is clear, and count on your reader's reaction to be where the sudden shock takes place.
What's very common is to put emphasis on the realization, on that moment the penny drops. "Suddenly" can do that - but there are other great shorthand methods.
Surprises are great, so are other stuff
You write you use "suddenly" for scene changes; that's fine. If you feel like you're overusing it, though, your problem may be less the particular phrasing and more the breakneck pace. If you feel you've got a lot of scene changes happening "suddenly," that might give your story an abrupt, disjointed feel. The reader may feel you're jerking scenes around arbitrarily - that the story doesn't build naturally from one scene to the next; instead, it's constantly being interrupted.
So maybe instead of using surprise from one scene to the next, try something else. Suspense is great - that's almost the opposite of surprise; it's openly building up to a big climax. There's lots of other tools in your toolbox - try things that let your characters take the initiative; try things that give your story a change of pace (or a lull you can interrupt more dramatically later); try a ticking timebomb to increase peril over the whole story instead of a bomb going off every time the story slows down.
Don't sweat some repetition
"Suddenly" is not an obtrusive word you need to be concerned about using twice in a chapter. It's also got plenty of innocuous uses - intended less to surprise than to simply describe ("the deck gave a sudden lurch," "I suddenly remembered I'd forgotten to hand in my homework," etc. etc.). And sometimes it's plenty useful when it does help with a surprise; that's natural and not really bothersome. So don't worry if you're not managing to weed out all of them; you can leave plenty in before they become a real problem.