It will require re-encrypting, yes. So give it a little test and see if it helps first.
It is possible to get rclone to server side move all the files which means you don't need to upload and download with a bit of cleverness.
What you do is make a new crypt backend copied from the old one, but with the new filename_encoding and a new destination directory.
You can then do rclone move oldcrypt: newcrypt: --crypt-server-side-across-configs and it should just move all the files into place for you without upload and download.