Musannaf Ibn Abi Shayba 34:227

Surayj ibn al-Nu‘man narrated to us, ‘Abd al-‘Aziz ibn Abi Salamah narrated to us, from Salih ibn Kaysan, he said: al-Raqashi informed us, from Anas, he said: The angels met Adam while he was circumambulating the House (the Kaaba). They said, "O Adam, have you performed Hajj?" He said, "Yes." They said, "We performed Hajj two thousand years before you."