I don’t think field level permissions is the correct solution to this. A relationship is actually two fields (one at each end) so it begs the question which field governs the permissions.
I think a more plausible solution is that the capabilities available in custom access templates get expanded so that the current ‘Edit’ capability (which encompasses the ability to link/unlink items) is split into a limited ‘Edit’ and a separate ‘Link/Unlink’ capability.
No idea of if/when this will happen though.