음...일단 relationship을 대체할만한 걸로는 bond를 추천하고 싶네요. 더 간단(?)하기도 하고, relationship은 좋은건지 나쁜 관계인지 그 용어만으론 알 수 없는 가치중립적인 단어인 반면, bond는 끈끈하게 서로 묶인 그 무엇을 뜻하니까요. 보통 bond는 strong, stronger을 쓰지만, deep도 가능하구요.
With more and more memories together, our bond becomes deeper.
또는
As we make more memories together, our bond will become deeper.
정도에서 표현할 수 있을 것 같아요.