We propose a Multi-Channel Pure Collective Aloha (MC-PCA) MAC protocol for asynchronous satellite uplink random access in this paper. The MC-PCA MAC protocol collects a batch of packets before selecting a channel randomly out of a number of channels and transmits these packets sequentially in the selected channel at one go. The key idea in the design of this proposed MC-PCA MAC protocol is to spread out the arrivals of each batch of packets across multiple channels. The proposed MAC protocol is analyzed theoretically and the analytical results are verified with simulation results. Theoretical results show that the maximum normalized throughputs of the MC-PCA MAC protocol can be up to doubled those of the Multi-Channel Pure Aloha (MC-Pure Aloha) MAC protocol with the same number of channels and with a large batch packet size. That is, the maximum normalized throughput gains for the MC-PCA MAC protocol over those for the MC-Pure Aloha MAC protocol can be up to 100% better. Numerical results show that maximum normalized throughputs of the MC-PCA MAC protocol over those for the MC-Pure Aloha MAC protocol are about 90% better with a typical batch packet size.