Does changing "sa" password require a SQL restart (in mixed mode)?

Q1: Does changing the sa password require a SQL restart?

No, but changing the authentication mode does. Since you're just changing the password and the authentication mode is already set to mixed, you're good to go with just changing the password.

Q2: Can I change the sa password the "normal" way?

Yes, it's just another SQL Login account.

Q3: Should we try to do this password rotation on a regular basis? Or only when we find an issue?

To be quite honest, I would disable and rename the SA login. This way it won't be used, at all and if you need a highly privileged login, then you can make one as needed.

This is a closing the barn door after the horses already ran off question.

You should have renamed and disabled the sa account when you built the instance.

Any time you have a well-known account, like administrator on a Windows system or sa for SQL Server, you should take certain steps to secure it. Let's look at specifically what you should do with sa:

Set a hard to guess password.

Rename sa.

Disable sa.

Ensure that no other accounts exist named sa.

Source

If you are keeping the 'sa' account as an emergency way to get SQL access there are safer ways see: Connect to SQL Server When System Administrators Are Locked Out If you don't have network account access, you have bigger problems then not being able to connect to SQL.