The fastest way to eliminate fear is to practice. I had the team go through it one day. They didn't get a choice. I locked us on a screen share until everyone was comfortable with how rebasing works. The call lasted maybe 90 minutes. You just have to decide one day that you (or the team) will master this shit, spend a few hours doing it, and move on.

Rebase is a super power but there are a few ground rules to follow that can make it go a lot better. Doing things across many smaller commits can make rebase less painful downstream. One of the most important things is to learn that sometimes a rebase is not really feasible. This isn't a sign that your tools are lacking. This is a sign that you've perhaps deviated so far that you need to reevaluate your organization of labor.