Fast irreversible transformation/compression of short messages using a secret
In the first part of this answer, I restrict to reading requirement 2 as &quot;if one pair $(m,r)$ is known…&quot;, and assume that $k$ is chosen at random. I entirely disregard security when an adversary knows two distinct pairs $(m,r)$, or when related keys $k$ are used.
The following construction uses the Galois Field $(\mathbb F_{2^{64}},\oplus,\otimes)$, with some irreducible polynomial¹:
$$f:\{0,1\}^{64}\times\{0,1\}^{128}\to\{0,1\}^{64}\\
(m,k)\mapsto (k_1\otimes m)\oplus k_0=r\\
\text{ where }\ k_1\mathbin\|k_0=k\ \text{ and }\ |k_0|=64=|k_1|$$
Given $(m,r)$ and $(m_1,r_1)$ with $m\ne m_1$, there exists a unique² key $k$ with $f(m,k)=r$ and $f(m_1,k)=r_1$. It follows that the construction perfectly meets it's security objective, regardless of the computational power of adversaries.
Note: For any fixed $k$ with $k_1\ne0$, there are no collisions.
Note: We wan restrict to a smaller output by removing any number of bits from the the result. We can correspondingly shorten the key $k$ by removing the bits of $k$ (in $k_0$) that do not influence the result.
Note: Computation of $f$ is simple and efficient on a CPU with built-in support for binary field arithmetic, including most modern x86 CPUs, which have carry-less multiplication. There's little point to this method otherwise.
#include &lt;stdint.h&gt;
#if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later.
#include &lt;immintrin.h&gt;
inline uint64_t f(uint64_t m, const uint64_t k[2]) {
  __m128i u,v;
  u.m128i_u64[0] = k[1];
  u.m128i_u64[1] = 27;                  // X**64 + x**4 + x**3 + x + 1
  v.m128i_u64[0] = m;
  v = _mm_clmulepi64_si128(u, v, 0);    // u.m128i_u64[0] * v.m128i_u64[0]
  u = _mm_clmulepi64_si128(u, v, 17);   // u.m128i_u64[1] * v.m128i_u64[1]
  return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0];
}
#else // no _mm_clmulepi64_si128
#pragma warning(disable : 4146)         // silence silly compiler's warning
uint64_t f2(uint64_t m, const uint64_t k[2]) {
  uint64_t a = k[1], x = (m &amp; -(a &amp; 1)) ^ k[0];
  a = (a &gt;&gt; 1) | (1ull &lt;&lt; 63);          // insert sentinel
  do                                    // 63 times
    x ^= (m = (27 &amp; -(m &gt;&gt; 63)) ^ (m + m)) &amp; -(a &amp; 1);
  while ((a &gt;&gt;= 1) != 1);
  return x;
}
#endif


Now I read requirement 2 as &quot;if some number of pairs $(m,r)$ are known…&quot;. If said number is large (larger than we are willing to process 64-bit key blocks), we can no longer build a perfectly secure system.
What the question asks can be nicely solved with a 64-bit block cipher, but then there is the question of choosing it. TEA? RC5? Blowfish? Prince? Simon? Speck? One of the lightweight crypto candidates? Any will do. And then we could venture into something custom.

¹ e.g. $x^{64}+x^4+x^3+x+1$, see Joerg Arndt's Binary irreducible polynomials with lowest-most possible set bits. This polynomial happens to also be primitive, but we do not need that property.
² Proof: that $k$ can be found as $k_1\gets(r\oplus r_1)\oslash (m\oplus m_1)$, $k_0\gets(k_1\otimes m)\oplus r$, $k\gets k_1\mathbin\|k_0$.