In my case: values.shape = (386363948, 2), k = 190973, the following code works fairly fast, 0.1 ~ 0.2 second.
indice = random.sample(range(386363948), 190973)
indice = torch.tensor(indice)
sampled_values = values[indice]

Using torch.randperm, however, would cost more than 20 seconds.
sampled_values = values[torch.randperm(386363948)[190973]]