How to handle a Drupal core change that have an impact in the next release of a contrib module?
There is no need for a new branch in your module as long as your own API doesn't change IMHO. The version definition will prevent that users update too early.
There is also no need to continue providing versions compatible with old core versions, they are no longer supported.

If it's just about deprecated usages, there's no reason to hurry, you can easily wait a few month/next core minor before starting to use it to give your users time to update. All those deprecated functions will only be removed in the 9.x branch, so you have plenty of time to update. It's different if core broke something in your module and you're forced to update asap or if there is a completely new API that you'd want to use.

See also last paragraph on PHP 7.1 requirement for Doctrine packages: Their PHP version dependency is similar to your Drupal core dependency.