The simplest option is to add a user key, yes.
Another option is to create a machine user with access only to the repos you need and add its user key to the build.
One more option would be to generate a deploy key for this other project on GitHub and then add it to CircleCI on the SSH permissions tab in your project’s settings.
Please let me know if any of those options works for you.