A network node, a wireless device and methods for use in a Random Access, RA, procedure with wireless devices in a cell of the network node. The method of the network node comprises receiving, from at least two wireless devices, a RA message having an RA preamble; transmitting an RA Response, RAR, to the wireless devices, the RAR having a TC-RNTI and an RA preamble identifier identifying the received RA preamble; and receiving, from each of wireless the devices, a connection request message having a respective S-TMSI. For a wireless device previously connected to the network node in the same cell, a connection setup message addressed to a C-RNTI previously assigned to the wireless device is transmitted. For a wireless device not previously connected to the network node in the same cell, a connection setup message addressed to the TC-RNTI is transmitted.