Evolution doesn't take millions of years for fast reproducing microbes. Another example is Covid, we've already seen half a dozen evolutions (that we know about) within the past several years.
To add to this, evolution typically happens _all at once_. Change does take a very long time but most of that time is spent in statis: everything has found its niche and lives in an equilibrium.
Once the environment changes (such as by introducing a whole new kind of food) species can very quickly adjust to the new reality.
