Hi Andrei,
It's easier to 'upload' new metadata ( which has new cert included ) of SP instead of uploading cert only in TR.
That means:
- Push your new cert in SP configuration.
- Make sure your SP is reflecting new cert in it's metadata.
- Grab that metadata and upload in trust relationship.