Incase its helps others.
Solution (for the time being):
1. Remove the existing connection, even though its being used by multiple flows.
2. Create a new SQS connection with the appropriate values
3. Open all the individual flows for edit, power automate will prompt the user to pick the sqs connection.
4. Select the new SQS connection and save.
At the moment, this is the solution that worked for me. The drawback being the need to manually open and save all the flows involved.