Passing the message via the redirect function is deprecated, but both redirect() and enqueueMessage() are still both fine to use on their own.
You simply need to use both together, like so:
$app = JFactory::getApplication();
$app->enqueueMessage('Redirect to another page was successful', 'success');
The best thing to do is to handle all redirects directly in sub controllers where you just need to use $this->setRedirect($url,$msg,$type); and MVC will do the rest of the job.
If you need to redirect outside of controllers you can use JControllerLegacy class:
$controller = JControllerLegacy::getInstance("ComponentName");
You may find using the proper/current classes will also help you in getting your code base up to current levels and ready for Joomla 4, which in turn might highlight some old functions that you need to look at.
I followed the instructions on https://groups.google.com/forum/#!topic/joomla-dev-general/el58Gh_6wUg to generate the file of deprecated classes ...
Yes, it's still being deprecated.
JError::raiseError() should be replaced with native exceptions.
JError::raiseWarning() and JError::raiseNotice should be replaced with calls to application's enqueueMessage() method to display warnings/notices.
See Potential backward compatibility issues in Joomla 4 for code migration tips.