Is it possible to change this message
Sorry this site is not shared with you
to something else when users don't have permissions?
It is recommended not to modify the OOB things or content. I would say to go with your custom access denied page. To do this, in SP2013 we have a bug and can achieve using HTTPModule. Please look into the following URL for more details.
Please let me know if you have any queries.