Faster-than-Nyquist (FTN) signaling aided non-orthogonal multiple access (NOMA) is conceived and its achievable rate is quantified in the presence of random link delays of the different users. We reveal that exploiting the link delays may potentially lead to a signal-to-interference-plus-noise ratio (SINR) gain, while transmitting the data symbols at FTN rates has the potential of increasing the degree-of-freedom (DoF). We then unveil the fundamental trade-off between the SINR and DoF. In particular, at a sufficiently high symbol rate, the SINR gain vanishes while the DoF gain achieves its maximum, where the achievable rate is almost $(1+β)$ times higher than that of the conventional synchronous NOMA transmission in the high signal-to-noise ratio (SNR) regime, with $β$ being the roll-off factor of the signaling pulse. Our simulation results verify our analysis and demonstrate considerable rate improvements over the conventional power-domain NOMA scheme.