In general, it is a bad idea to have long clustered index keys. For that it is not important if the key is made up of several short columns or few long columns. This makes the maintenance of every index as well as the read access of every index on that table a lot more expensive that it has to be. As the PK is by default enforced by a clustered index, you most likely have a very long clustered index key.
Also in general it is a good idea to have you clustered index key be monotonously increasing. As your column is valued based on NEWID it will distribute new rows all over the table causing fragmentation. The extra long key will make this even worse.
And finally, in general it is a good idea to not spend too much time tuning performance preemptively. If you do new development follow best practices (like the two recommendations above). With existing software, fix only the stuff that is causing a headache.
Now it looks like you have that headache already. Therefore I would start by migrating those primary keys to either identity columns (preferred) or to uniqueidentifier columns that default to newsequentialid().
But this is a difficult change to do if you can't take downtime. I that case I would start by adding new indexes to support you current strongest headache (read: stored procedure). Than work on cleaning up the mess afterwards.