We also recently got this message from Apple, which is quite an issue for us as our build nodes were not capable of running Xcode 13, and further their own previous posts on the issue only suggested that in order to upload to the App Store apps were required to be built with Xcode 13 after Apr 25, not that they also required linking against the iOS 15 SDK, or that apps already uploaded to the app store before the deadline would require this to be approved for release.
We're half way through upgrading our build machines to run a version of MacOS that supports Xcode 13 (causing various issues with other parts of our build of course), installing Xcode 13, and now we have to work out how to upgrade our Xcode project to use the iOS 15 SDK without it breaking even more stuff (actually, initial investigation suggests we don't need to change our project settings at all, it will happen automatically). Happy days, but that's Apple for you (in contrast, most of our MS-stack-based and Android-based applications are using quite old and in some cases out-of-LTS versions of various libraries and build tools, as we haven't had the resources to upgrade yet, but certainly haven't any issues with publishing or running them).