Inventory models with lost sales and large lead times are notoriously difficult to manage due to the curse of dimensionality. It has been recently proved that in the lost-sales inventory model with divisible products, as the lead time grows large, a simple open-loop constant-order policy is asymptotically optimal. In this paper, we consider the lost-sales inventory model in which the lead time is not only large but also random. Under the assumption that the placed orders cannot cross in time, we establish the asymptotic optimality of constant-order policies as the lead time increases for the model with divisible products. For the model with indivisible products, we propose an open-loop bracket policy, which alternates deterministically between two consecutive integer order quantities. By employing the concept of multimodularity, we prove that the bracket policy is asymptotically optimal. Our results on divisible products also hold for the models with order crossover and random supply functions. Finally, we provide a numerical study to demonstrate the good performance of the proposed open-loop policies and derive further insights.