We propose a new protocol to implement ultra-fast two-qubit phase gates with trapped ions using spin-dependent kicks induced by resonant transitions. By only optimizing the allocation of the arrival times in a pulse train sequence the gate is implemented in times faster than the trapping oscillation period T < 2pi/omega. Such gates allow us to increase the number of gate operations that can be completed within the coherence time of the ion-qubits favoring the development of scalable quantum computers.