TL;DR: Because the prequels are trying to make a point about the Jedi's failures in part through the hierarchy of the Jedi Order, in which Grand Master Yoda sits atop as the Jedi's primary leader.
I agree with many of the other answers here, but I want to unpack some of it a little more...
The structures of the prequels each features a villain with characteristics of either the future Darth Vader or Anakin Skywalker (with Darth Sidious hiding behind them).
Moreover, each film also has a seasoned Jedi Master fearful of Anakin Skywalker. In The Phantom Menace it is Yoda. In Attack of the Clones it is Obi-wan Kenobi, in Revenge of the Sith it is Mace Windu. All of their indecisiveness plays into Anakin's downfall.
But Yoda's trajectory is the most interesting, as he starts out not wanting to train Anakin, fearful of his clouded force vision of Anakin's future. The death of Qui-gon Jin seems to change his mind.
In the second film is when Yoda takes a real enlightened step back when he tells Obi-Wan that the older Jedi have become more arrogant, which is later followed through when younglings help Obi-wan find his lost star. He then also corrects Obi-wan's statement that the clone army was a victory, as the shroud of the dark side has fallen. Then the clone wars occur and he seems to loose his way again.
So why was he surprised in Revenge of the Sith upon confronting Darth Sidious?
It's not surprised in the sense that he didn't know that the Sith had returned or that the council hadn't suspected Palpatine, as they wanted Anakin to spy on him. But it was a surprise or really more of shock, because Yoda didn't realize HOW POWERFUL of a Sith Lord he was dealing with, given the death of Mace Windu and the turn of Anakin Skywalker. It took a lot of time and patience for Palpatine's/Sidious' plan to be executed. And Darth Sidious once again reminds Yoda of his own arrogance and ultimate failure as they begin to fight. Basically, things just got real.
However, Yoda's force vision and capacity to use the Force was also clouded because the Jedi Temple on Coruscant unknowingly sat on top of a Sith Shrine, which feeds into his shock once actually confronting Darth Sidious.
In addition Star Wars is about to launch "Project Luminous" (now pushed to the beginning of 2021). Starting in publishing with books and comics, Project Luminous takes place 200 years before the Skywalker Saga in the High Republic Era and is about the Jedi during their prime, as certain sect begin to explore the new frontier on the outer rim and unknown regions before facing something that threatens their existence and The Force!
Given that Yoda would be a much younger Jedi at this time AND given we do not yet have a "canonical" backstory on the rise or plights of Darth Plagueis, it's not hard to speculate that eventually the High Republic Era may inform and layer back onto the Skywalker Saga, putting some of it into a new context. Specifically how these "Knights of the Round Table" Jedi became the fearful and more frugal Jedi of the Skywalker Saga!
After all, if Darth Plagueis did exist and was Darth Sidious' master, then how could the Sith NOT have existed for thousands of years? A force DYAD across space-time? Maybe, but it seems more likely that there is cover-up story between different eras of Jedi, with Yoda possibly being one member who has kept a sizable secret. If so, then this too would add great weight onto his surprise, shock, and failure of the Jedi Order of his time and not really believing it, until he had seen it, based on what he thought he knew or didn't, before.