You say that the "behaviour" isn't optimal, but you don't clarify whether the actual interface is a problem or not.

Is "behaviour" what's happening behind the scenes that if you change it, it'll affect the interface the user uses or the results/returns/output? If not, make the changes, make sure all existing tests pass, write new tests, and you're good to go.

Otherwise, if the user experience will change, as LanX said, you have a few options:

Write a brand new distribution, deprecate the old. In the old one, point loudly to the new one for new users

Add new functions/methods alongside the existing ones that are already in use. Deprecate the latter ones, leave them for back-compat, but promote the new subs for new users, and existing users who may one day update their own software

Add new flag(s) to the existing subs, so that the different "behaviour" is called behind the scenes if the user sets this flag.

I'd stay away from the last option though, as personally I see it only as a stop-gap for a transition into something new. It'll add complexity to the already inefficient behaviour you've already got.

As far as time frame, I'd give at least one year for providing critical updates (security, data corruption etc), then at that time, change the notice from deprecated to unmaintained.