iOS 13 SDK deadline confusion for existing released apps

Do I need to re-build and re-submit just to meet this requirement in order to keep my app on the App Store?

No. If you have no pressing need to release an app update, no action is needed on your part. The message applies only to developers who are either working on releasing a new app or an update to an existing app on the App Store.

Or do they only mean this is required for new app updates submitted?

Yes.

The message simply means that any developer looking to either release a new app or an update to an existing app on the App Store will have to build it using iOS 13 SDK starting April 30, 2020. The last message mean that the said deadline has been extended to June 30, 2020.

You can still release a new app or an update using iOS 12 SDK till June 29, 2020. (In your case, as your last release is built using iOS 12 SDK.)

Again, no action is needed on your part if there's no change in your app. Also, you can still release an app update, till June 29, 2020, using iOS 12 SDK.

Even starting June 30, 2020, no action would be required from your part. But past that point, any update that you wish to submit would be required to be built using iOS 13 SDK (Xcode 11).