In this work, we present the first secure steganographic protocol in the common computational model which, for any communication channel (of sufficiently large min-entropy), is provably secure, reliable, and has nearly optimal bandwidth, but needs super-polynomial time. This solves several open problems in the secret-key steganography in the common computational model. In particular, our result answers affirmatively the question whether there exists a secure and reliable universal system of rate asymptotically larger than \log \kappa, where \kappa is the security parameter defining the length of the secret-key. Next, we prove a lower bound on the query complexity of stegosystems showing that our construction is optimal. This lower bound extends the results by Hopper et al. [IEEE, Trans.~on, 2009] and by Dedic et al. [J.~Cryptology, 2009]. We discuss also the universal steganography of optimal rate in the information-theoretic setting. We prove that an exponential number of samples is needed to embed messages in documents of high min-entropy. Our results, together with the result by Cachin [Inf.~Comput,~2004], show that the situation of universal steganography in the computational and in the information-theoretic model is analogous: such universal steganography exists, but the protocols need superpolynomial time; On the other hand, restricting stegosystems to polynomially time bounded, universal steganography of optimal rate is not possible in both settings.